#ifndef _TRIANGULATION_H_
#define _TRIANGULATION_H_

#define CGAL_CT2_WANTS_TO_HAVE_EXTRA_ACTION_FOR_INTERSECTING_CONSTRAINTS	
#define CGAL_CDT2_EXTRA_ACTION_FOR_INTERSECTING_CONSTRAINTS (throw std::exception());

#include <vector>
#include <algorithm>
#include <cmath>

#ifdef WIN32
#include <Windows.h>
#endif
#include <GL/GL.h>
#include <GL/GLU.h>

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_vertex_base_2.h>
#include <CGAL/Triangulation_face_base_2.h>
#include <CGAL/Triangulation_hierarchy_2.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
#include <CGAL/Constrained_triangulation_face_base_2.h>
#include <CGAL/enum.h>
#include <CGAL/number_utils.h>
#include <CGAL/Vector_2.h>

#include "../common/polytope.h"
#include "../common/error_info.h"

namespace Packing
{

	using namespace Packing_common;

	template < class Gt, class Vb = CGAL::Triangulation_vertex_base_2<Gt> >
	class Vertex_2 : public Vb
	{
	public:
		typedef typename Vb::Vertex_handle Vertex_handle;
		typedef typename Vb::Face_handle Face_handle;
		typedef typename Vb::Point	Point;

		template < typename TDS2 >
		struct Rebind_TDS
		{
			typedef typename Vb::template Rebind_TDS<TDS2>::Other Vb2;
			typedef Vertex_2<Gt, Vb2> Other;
		};

	public:
		Vertex_2() : Vb() { group_id = -1; }
		Vertex_2(const Point& p) : Vb(p) { group_id = -1; }
		Vertex_2(Face_handle f, const Point& p) : Vb(f, p) { group_id = -1; }
		Vertex_2(Face_handle f) : Vb(f) { group_id = -1; }

	public:
		int group_id;
		std::vector<Point> voronoi_vtx;
		std::vector<Point> cat_vtx;
	};

	template < class Gt, class Fb = CGAL::Constrained_triangulation_face_base_2<Gt> >
	class Face_2 : public Fb
	{
	public:
		typedef typename Fb::Vertex_handle Vertex_handle;
		typedef typename Fb::Face_handle Face_handle;
		template <class TDS2>
		struct Rebind_TDS
		{
			typedef typename Fb::template Rebind_TDS<TDS2>::Other Fb2;
			typedef Face_2<Gt, Fb2> Other;
		};
	public:
		Face_2() : Fb() { }
		Face_2(Vertex_handle v0, Vertex_handle v1, Vertex_handle v2) : Fb(v0, v1, v2) { }
		Face_2(Vertex_handle v0, Vertex_handle v1, Vertex_handle v2,
			Face_handle f0, Face_handle f1, Face_handle f2) : Fb(v0, v1, v2, f0, f1, f2) { }

		CGAL::Sign normal_orientation;
	};

	// plain delaunay triangulation definition
	typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
	typedef CGAL::Triangulation_hierarchy_vertex_base_2< Vertex_2<Kernel> > Vbh;
	typedef CGAL::Triangulation_data_structure_2< Vbh, Face_2<Kernel> > TDS2;

	class Constraint_Delaunay_triangulation_2 : public CGAL::Constrained_Delaunay_triangulation_2< Kernel, TDS2 >
	{
	};

	// triangulation between polygons/polyhedron by sampling on edges
	class Polygon_triangulation
	{

		typedef Constraint_Delaunay_triangulation_2::Edge_circulator Edge_circulator;
		typedef CGAL::Vector_2<Constraint_Delaunay_triangulation_2::Geom_traits> Vector_2;

	public:
		typedef Constraint_Delaunay_triangulation_2::Point Point;
		typedef Constraint_Delaunay_triangulation_2::Segment Segment;
		typedef Constraint_Delaunay_triangulation_2::Vertex_handle Vertex_handle;
		typedef Constraint_Delaunay_triangulation_2::Face_circulator Face_circulator;
		typedef Constraint_Delaunay_triangulation_2::Edge_iterator Edge_iterator;
		typedef Constraint_Delaunay_triangulation_2::Vertex_iterator Vertex_iterator;
		typedef Constraint_Delaunay_triangulation_2::Face_iterator Face_iterator;
		typedef Constraint_Delaunay_triangulation_2::Finite_faces_iterator Finite_faces_iterator;

		typedef std::vector<Vertex_handle> Vert_group;

	public:
		Polygon_triangulation(const std::vector<Point>& boundary_vertices, unsigned int sample_nb = 50);
		void insert_polygons(const std::vector<Packing_polygon*>& polygon_set, unsigned int sample_nb = 20);
		// insert boundary points in sequence
		//void insert_boundary(const std::vector<Point>& boundary_vertices);
		
		// traversal methods
		Vertex_iterator vertices_begin() { return dt.vertices_begin(); }
		Vertex_iterator vertices_end() { return dt.vertices_end(); }
		Edge_iterator edges_begin() { return dt.edges_begin(); }
		Edge_iterator edges_end() { return dt.edges_end(); }
		Face_iterator faces_begin() { return dt.faces_begin(); }
		Face_iterator faces_end() { return dt.faces_end(); }

		template <class IteratorType> bool is_infinite(IteratorType it) const { return dt.is_infinite(it); }
		template <class FaceIterator> inline bool is_intergroup_face(FaceIterator fc) const
		{
			Vertex_handle v0 = fc->vertex(0), v1 = fc->vertex(1), v2 = fc->vertex(2);
			return (!(v0->group_id == v1->group_id && v0->group_id == v2->group_id && v1->group_id == v2->group_id));
		}

		const Vert_group& vertex_at_group(unsigned int idx) const { return vgroups[idx]; }
		void transform_vertex_at_group(unsigned int id, const Parameter& p);
		//inline bool is_intergroup_face(Face_circulator fc) const;
		void bisector_at_vertex(Vertex_handle v, std::vector<Point>& voronoi_vertices) const;
		void cat_at_vertex(Vertex_handle v, std::vector<Point>& cat_vertices) const;		

		void gl_draw_triangulation(const GLfloat* color) const;
		void gl_draw_intergroup_cat(const GLfloat* color/*, unsigned int group_id*/) const;
		void gl_draw_intergroup_voronoi(const GLfloat* color/*, unsigned int group_id*/) const;

		void clear();

	private:
		void construct_voronoi_cells();
		void construct_cat_cells();

	private:
		Constraint_Delaunay_triangulation_2 dt;
		std::vector<Vert_group> vgroups;
		std::vector<Point> boundary_pnts;
	};
}

#endif